Introduction

The Diffie-Hellman key exchange protocol allows two parties, Alice and Bob, to agree on a secret key without having exchanged any secret information beforehand! The method is based in cyclic groups, so read up on that in the mathematical prerequisites.

Diffie-Hellman Key Exchange

The protocol itself is based on the group $Z_{p}^{*}$ , where $p$ is some huge prime number. The prime numbers that can be used in the Diffie-Hellman (DH) key exchange are standardised - they are public knowledge and can be found in various RFCs on the Internet. More specifically, the prime $p$ must be a safe prime, i.e. a prime such that $p = 2 q + 1$ , where $q$ is also prime.

Example: Diffie-Hellman Primes

One such prime $p$ can be found in RFC 3526 and is 4096 bits long.

Notice that since $p = 2 q + 1$ , the prime $q$ divides $p - 1$ and so the group $Z_{p}^{*}$ has an element $g$ of order $q$ and the powers of $g$ generate the group $⟨ g ⟩ : = {0, 1, \dots, q - 1}$ . It turns out that this group $⟨ g ⟩$ is a subgroup of $Z_{p}^{*}$ . We are now ready to outline the DH key exchange.

The primes $p, q$ as well as the generator $g$ are public knowledge and are standardised in various RFCs.

Alice picks a random power between $0$ and $q - 1$ , i.e. a uniform $a \leftarrow_{R} Z_{q}$ and computes $A : = g^{a}$ . Similarly, Bob picks a uniform $b \leftarrow_{R} Z_{q}$ and computes $B : = g^{b}$ . Alice and Bob then exchange the values $A$ and $B$ which they computed - Alice obtains $B$ from Bob and Bob obtains $A$ from Alice.

Alice now computes $B^{a} = (g^{b})^{a} = g^{ab}$ and Bob computes $A^{b} = (g^{a})^{b} = g^{ab}$ - the two parties have arrived at the same key $k : = g^{ab}$ ! Interestingly enough, any eavesdropping adversary cannot arrive at the same value by just observing the communication channel, since they do not know the secret values $a$ and $b$ which Alice and Bob picked separately for themselves.

	Alice	Bob	Eve
$p$	known	known	known
$q$	known	known	known
$g$	known	known	known
$a$	known	unknown	unknown
$b$	unknown	known	unknown
$g^{a}$	known	known	known
$g^{b}$	known	known	known
$g^{ab}$	known	known	unknown

The Diffie-Hellman Problems

The security of the Diffie-Hellman protocol is defined according to certain mathematical problems.

In trying to break the Diffie-Hellman key exchange, the adversary Eve is in a way trying to solve the discrete logarithm problem. The function $Dlog_{g}$ denotes the discrete logarithm function with base $g$ and is the function that returns the power $x \in Z_{q}$ which you need to raise $g$ to in order to obtain $g^{x}$ , i.e. Eve is trying to compute $Dlog_{g} (g^{x})$ . The logarithm is called discrete because it only returns integer values due to the fact that we are working with groups

Definition: The Discrete Logarithm Problem

The adversary $Eve$ is given the generator $g$ as well as the order $q$ of the generated group $⟨ g ⟩$ and is provided with the group element $g^{x}$ for some uniform, unknown, $x \leftarrow_{R} Z_{q}$ . Her goal is to find the value of $x$ .

We say that the discrete logarithm problem is hard relative to $⟨ g ⟩$ if no matter what Eve does, the probability that she can find $x$ is negligible, i.e.

$x \leftarrow_{R} Z_{q} Pr [Eve (g, q, g^{x}) = x] \leq negl (\cdot)$

It should be obvious that the computational difficulty of the discrete logarithm largely depends on the group itself and so not every group yields a secure Diffie-Hellman key exchange.

There are two additional problems which are similar to the discrete logarithm problem and are known to be related but not equivalent to the each other.

Definition: The Computational Diffie-Hellman (CDH) Problem

The adversary $Eve$ is given the generator $g$ as well as the order $q$ of the generated group $⟨ g ⟩$ and is provided with two group elements $g^{a}$ and $g^{b}$ for some uniform, unknown, $a, b \leftarrow_{R} Z_{q}$ . Her goal is to then find the value of $g^{ab}$ .

We say that the computational diffie-hellman problem is hard relative to $⟨ g ⟩$ if, no matter what Eve does, the probability that she can find $g^{ab}$ is negligible, i.e.

$a, b \leftarrow_{R} Z_{q} Pr [Eve (g, q, g^{a}, g^{b}) = g^{ab}] \leq negl (\cdot)$

The CDH problem is essentially an exact description of the Diffie-Hellman scenario. Eve can observe the communication between Alice and Bob and is thus able to obtain the values $g^{a}$ and $g^{b}$ . However, Alice and Bob ultimately end up using the value $g^{ab}$ as a key and so Eve has to find a way to compute it using only $g^{a}$ and $g^{b}$ .

The second problem is related to the CDH problem but the two problems are not known to be equivalent.

Definition: The Decisional Diffie-Hellman (DDH) Problem

The adversary $Eve$ knows the cyclic group $G$ , one of its generators $g$ and its order $q$ . She is given two group elements $g^{α}, g^{β}$ which are generated by $g$ for some uniform, unknown to Eve, powers $α, β \leftarrow_{R} Z_{q}$ . Finally, Eve is either given a third such element $g^{γ}$ generated by some uniform unknown $γ \leftarrow_{R} Z_{q}$ or she is given the element $g^{α β}$ . Eve's goal is to then determine if she has $g^{α β}$ or $g^{γ}$ .

We say that the DDH problem is hard relative to $G$ if no matter what Eve does, the probability that she achieves her goal is negligible, i.e.

$Pr [Eve (G, g, q, g^{α}, g^{β}, g^{γ}) = 1] - Pr [Eve (G, g, q, g^{α}, g^{β}, g^{α β}) = 1] \leq negl (\cdot)$

If the CDH problem is easy relative to some group, then so is the DDH problem.

The Cyberclopaedia

Introduction

Diffie-Hellman Key Exchange

The Diffie-Hellman Problems